package bin_tree;

import my_bts.MyBTS;

import java.util.*;

/**
 * 基础二叉树
 */
public class MyBinTree {
    /**
     * 二叉树节点定义
     */
    public static class BinTreeNode {
        public Character val;
        public BinTreeNode left;
        public BinTreeNode right;

        public BinTreeNode (Character val) {
            this.val = val;
        }
    }

    /**
     * 建造一个二叉树
     * @return 返回根结点
     */
    public static BinTreeNode build() {
        BinTreeNode nodeA = new BinTreeNode('A');
        BinTreeNode nodeB = new BinTreeNode('B');
        BinTreeNode nodeC = new BinTreeNode('B');
        BinTreeNode nodeD = new BinTreeNode('C');
        BinTreeNode nodeE = new BinTreeNode('D');
        BinTreeNode nodeF = new BinTreeNode('D');
        BinTreeNode nodeG = new BinTreeNode('C');
        BinTreeNode nodeH = new BinTreeNode('H');
        nodeA.left = nodeB;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeA.right = nodeC;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        return nodeA;
    }

    /**
     * 二叉树的前序遍历
     * @param root
     */
    public static void preOrder(BinTreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 使用迭代的方法对二叉树进行前序遍历
     * @param root
     * @return
     */
    public static List<Character> preorderTraversal(BinTreeNode root) {
        List<Character> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Deque<BinTreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            BinTreeNode node = stack.pop();
            ret.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return ret;
    }

    /**
     * 二叉树的中序遍历
     * @param root
     */
    public static void inOrder(BinTreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    /**
     * 中序遍历的迭代实现
     * @param root
     * @return
     */
    public static List<Character> inorderTraversal(BinTreeNode root) {
        List<Character> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Deque<BinTreeNode> stack = new ArrayDeque<>();
        BinTreeNode cur = root; // 用于标识左子树的遍历，若cur为空，则表明peek结点的左子树已遍历完毕不在重复遍历
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            ret.add(cur.val);
            cur = cur.right;
        }
        return ret;
    }

    /**
     * 二叉树非递归、非迭代mirrors方法
     * 当遍历到子树的最后一个右节点时不用层层返回，通过设置最后一个右节点的后继节点为需要返回的位置直接返回
     * @param root
     */
    public static void inorderMirrors(BinTreeNode root) {
        BinTreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) {
                // 说明没有左子树，走右子树
                // 不用担心没有右子树在这之前已经将叶子节点的右孩子设为了遍历完了它要返回的根节点
                System.out.print(cur.val + " ");
                cur = cur.right;
            } else {
                // 寻找当前根结点的前驱结点
                BinTreeNode pre = cur.left;
                // pre.right != cur为了防止死循环
                // 当pre.right == cur说明当前最后的右节点已经设置了输出它后的后继根节点
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }
                // 已经设置了后继节点，且是第二次遍历到该节点直接将其与后继节点断开，破除环
                // 且这个后继节点的左子树已经全部遍历输出完毕，之后走右子树
                if (pre.right == cur) {
                    System.out.print(cur.val + " ");
                    pre.right = null;
                    cur = cur.right;
                } else {
                    // 找到了最右节点，将其与寻找它的根结点建立联系
                    pre.right = cur;
                    // 继续寻找下一个节点的最右节点
                    cur = cur.left;
                }
            }
        }
    }

    /**
     * 二叉树的后序遍历
     * @param root
     */
    public static void postOrder(BinTreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    /**
     * 迭代实现二叉树的后序遍历
     * @param root
     * @return
     */
    public static List<Character> postorderTraversal(BinTreeNode root) {
        List<Character> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Deque<BinTreeNode> stack = new ArrayDeque<>();
        BinTreeNode cur = root;
        BinTreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (cur.right == null || cur.right == prev) {
                ret.add(cur.val);
                prev = cur;
                cur = null;
            } else {
                // 说明当前cur是根结点且右子树不为空，要开始遍历其右子树了
                stack.push(cur);
                cur = cur.right;
            }
        }
        return ret;
    }

    /**
     * 二叉树的层序遍历
     * @param root
     * @return
     */
    public static List<List<Character>> levelOrder(BinTreeNode root) {
        List<List<Character>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        // 使用队列辅助遍历
        Deque<BinTreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            // 使用curList保存该层元素
            List<Character> curList = new ArrayList<>();
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                BinTreeNode node = deque.poll();
                curList.add(node.val);
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
            ret.add(curList);
        }
        return ret;
    }

    /**
     * 计算以root为根结点的二叉树总的结点个数
     * @param root
     * @return
     */
    public static int countAllNnm(BinTreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + countAllNnm(root.left) + countAllNnm(root.right);
    }

    /**
     * 层序遍历求以root为根结点的二叉树的总结点个数
     * @param root
     * @return
     */
    public static int countAllNumLevel(BinTreeNode root) {
        if (root == null) {
            return 0;
        }
        int ret = 1;
        Deque<BinTreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            BinTreeNode node = deque.poll();
            if (node.left != null) {
                ret ++;
                deque.offer(node.left);
            }
            if (node.right != null) {
                ret ++;
                deque.offer(node.right);
            }
        }
        return ret;
    }

    /**
     * 计算以root为根结点的所有叶子结点的个数
     * @param root
     * @return
     */
    public static int countLeafNum(BinTreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return countLeafNum(root.left) + countLeafNum(root.right);
    }

    /**
     * 层序遍历求以root为根结点的所有叶子结点的个数
     * @param root
     * @return
     */
    public static int countLeafNumLevel(BinTreeNode root) {
         if (root == null) {
             return 0;
         }
         int ret = 0;
         Deque<BinTreeNode> deque = new ArrayDeque<>();
         deque.offer(root);
         while (!deque.isEmpty()) {
             int size = deque.size();
             BinTreeNode node = deque.poll();
             if (node.left == null && node.right == null) {
                 ret ++;
             }
             if (node.left != null) {
                 deque.offer(node.left);
             }
             if (node.right != null) {
                 deque.offer(node.right);
             }
         }
         return ret;
    }

    /**
     * 计算以root为根结点的树高
     * @param root
     * @return
     */
    public static int treeHeight(BinTreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(treeHeight(root.left) , treeHeight(root.right));
    }

    /**
     * 计算以root为根结点的二叉树的第K层有多少个结点
     * @param root
     * @param k
     * @return
     */
    public static int KLevelNum(BinTreeNode root, int k) {
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return KLevelNum(root.left, k - 1) + KLevelNum(root.right, k - 1);
    }

    /**
     * 判断二叉树是否为对称二叉树
     * @param root
     * @return
     */
    public static boolean isSymmetric(BinTreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<BinTreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            BinTreeNode leftN = deque.poll();
            BinTreeNode rightN = deque.poll();
            if (leftN == null && rightN == null) {
                continue;
            }
            if (leftN == null || rightN == null || leftN.val != rightN.val) {
                return false;
            }
            deque.offer(leftN.left);
            deque.offer(rightN.right);
            deque.offer(leftN.right);
            deque.offer(rightN.left);
        }
        return true;
    }

    /**
     * 二叉树的完全性检验
     * @param root
     * @return
     */
    public static boolean isCompleteTree(BinTreeNode root) {
        Deque<BinTreeNode> deque = new ArrayDeque<>(); // deque中不会给存储null
        boolean state = false; // 使用该状态标识二叉树的结点是否已经达到叶子结点
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();;
            for (int i = 0; i < size; i++) {
                BinTreeNode node = deque.poll();
                if (!state) {
                    // 非叶子结点状态
                    if (node.left != null && node.right != null) {
                        deque.offer(node.left);
                        deque.offer(node.right);
                    } else if (node.left != null) {
                        deque.offer(node.left);
                        state = true;
                    } else if (node.right != null) {
                        return false;
                    } else {
                        // 左右孩子结点都为空即已经是子结点
                        state = true;
                        deque.addFirst(node);
                    }
                } else {
                    // 叶子结点状态
                    if (node.left != null || node.right != null) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 求以root为根结点的二叉树的最大宽度
     * @param root
     * @return
     */
    public static int widthOfBinaryTree(BinTreeNode root) {
        int maxWidth = 0;
        if (root == null) {
            return maxWidth;
        }
        Deque<BinTreeNodeWithNum> deque = new ArrayDeque<>(); // 不存储null
        deque.offer(new BinTreeNodeWithNum(root, 1));
        while (!deque.isEmpty()) {
            int size = deque.size();
            int L = 0, R = 0; // 使用L、R分别表示每一层最左侧和最右侧对应的满二叉树的编号，涉及到编号给原二叉树结点类再加上一个二叉树编号属性
            for (int i = 0; i < size; i++) {
                BinTreeNodeWithNum node = deque.poll();
                if (i == 0) {
                    // node为该层最左侧结点
                    L = node.num;
                }
                if (i == size - 1) {
                    // node为该层最右侧结点
                    R = node.num;
                }
                if (node.node.left != null) {
                    int num = 2 * node.num;
                    deque.offer(new BinTreeNodeWithNum(node.node.left, num));
                }
                if (node.node.right != null) {
                    int num = 2 * node.num + 1;
                    deque.offer(new BinTreeNodeWithNum(node.node.right, num));
                }
            }
            maxWidth = Math.max(maxWidth, R - L + 1);
        }
        return maxWidth;
    }

    static class BinTreeNodeWithNum {
        BinTreeNode node;
        int num;

        BinTreeNodeWithNum (BinTreeNode node, int num) {
            this.node = node;
            this.num = num;
        }
    }

    /**
     * 递归计算二叉树的直径
     * @param root
     * @return
     */
    public static int diameterOfBinaryTree(BinTreeNode root) {
        if (root == null) {
            return 0;
        }
        int retL = 0, retR = 0;
        int L = treeHeight(root.left);
        int R = treeHeight(root.right);
        int l = L + R;
        if (root.left != null) {
            retL = Math.max(diameterOfBinaryTree(root.left), l);
        }
        if (root.right != null) {
            retR = Math.max(diameterOfBinaryTree(root.right), l);
        }
        return Math.max(retL, retR);
    }

    public static void main(String[] args) {
//        BinTreeNode root = build();
//        System.out.println("前序遍历的结果为：");
//        preOrder(root);
//        System.out.println();
//        System.out.println("中序遍历的结果为：");
//        inOrder(root);
//        System.out.println(Arrays.toString(inorderTraversal(root).toArray()));
//        inorderMirrors(root);
//        System.out.println();
//        System.out.println("后序遍历的结果为：");
//        postOrder(root);
//        System.out.println(Arrays.toString(postorderTraversal(root).toArray()));
//        System.out.println();
//        System.out.println("二叉树总结点个数为: " + countAllNnm(root));
//        System.out.println("层序遍历，二叉树总结点个数为: " + countAllNumLevel(root));
//        System.out.println("二叉树的叶子结点个数为: " + countLeafNum(root));
//        System.out.println("层序遍历，二叉树的叶子结点个数为: " + countLeafNumLevel(root));
//        System.out.println("树高为：" + treeHeight(root));
//        int k = 3;
//        System.out.println("第" + k + "层结点个数为：" + KLevelNum(root, k));
//        System.out.println("层序遍历的结果为：" + Arrays.toString(levelOrder(root).toArray()));
//        System.out.print("判断此树是否为堆成二叉树的结果为：" + isSymmetric(root));
//        System.out.println("检验二叉树的完全性结果为：" + isCompleteTree(root));
//        System.out.println(diameterOfBinaryTree(root));
        BinTreeNode root = new BinTreeNode('1');
        BinTreeNode node = new BinTreeNode('2');
        BinTreeNode node1 = new BinTreeNode('3');
        root.left = node;
        node.left = node1;
    }
}
